import java.util.*;

public class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n-k+1];
        int[] prefixMax = new int[n];
        int[] suffixMax = new int[n];

        // 先预处理前缀的数组
        for (int i = 0; i < n; i++) {
            if (i % k == 0) {
                prefixMax[i] = nums[i];
            } else {
                prefixMax[i] = Math.max(prefixMax[i-1], nums[i]);
            }
        }

        // 后缀数组
        for (int i = n-1; i >= 0; i--) {
            if (i == n-1 || (i+1) % k == 0) {
                suffixMax[i] = nums[i];
            } else {
                suffixMax[i] = Math.max(suffixMax[i+1], nums[i]);
            }
        }

        // 1. 窗口刚好包括这个分组
              //  这个时候窗口最大值是前缀的最后一个元素的预处理结果
        // 2. 窗口包含两个分组
        // 窗口最大值是 max(suffixMax[i], prefixMax[i+k-1])
        for (int i = 0; i < n-k+1; i++) {
            ans[i] = Math.max(suffixMax[i], prefixMax[i+k-1]);
        }
        return ans;

    }
    public static void main(String[] args) {
        int[] arr = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow(arr, 3)));
    }
}
